\section{\large Markov Logic Network as an Interface Layer for Testing-based Software Bug Localization}
\label{sec:interface}

We first discuss why an interface layer is needed in automated debugging research. Then, we
illustrate why Markov Logic Network can be a good fit.

\vspace{1mm}

\noindent \textit{\textbf{The need of an interface layer in software bug localization.}}
As pointed out in~\cite{mln}, if we look at other subfields of computer science, we see that
in most cases progress has been enabled above all by the creation of an interface layer that
separates innovation above and below it, while allowing each to benefit from the other.
A good interface layer exposes important distinctions and hides unimportant ones. 
Below the layer, research improves the foundations (or, more pragmatically, the infrastructure);
above it, research improves existing applications and invents new ones. For example,
in the programming language research community, new applications such as advanced
program analyses (above the layer) are
enabled by the invention of high-level programming languages
(the interface layer), and compilers and type system theories (below the layer)
continue to be proposed. In many other cases, the development of the interface layer
triggered a period of rapid progress above and below it. 

The need of an interface layer is also true for the automated bug localization research community, particularly
for testing-based bug localization. Being consistent with the notations in~\cite{mln},
testing-based bug localization can be roughly divided
into ``foundational” and ``application” areas. Foundational areas
include efficient program instrumentation~\cite{Ball:1996}, test suite creation~\cite{PachecoLEB2007},
data coverage data collection~\cite{Zhang:2004}, etc. Application areas include
anomaly identification~\cite{Gruska:2010}, software fault localization, predication~\cite{feng:learning} and fixing~\cite{JeffreyFGG09}, etc.
An ideal interface layer for testing-based bug localization should provide the former, and serve the latter.

However, in software bug localization research, the interface layer has been conspicuously absent, and this,
perhaps more than any other factor, has limited the rate of progress.
In practice, this limitation is often circumvented by manually transforming the 
low-level details (e.g., test coverage data) into an intermediate presentation (e.g,
the Tarantula~\cite{Jones02visualizationof} model).
Manual tweak and transformation of low-level details may be useful for specific
circumstances, but brings in the cost, brittleness, and lack of reusability 
that may still overweight its benefits.



\vspace{1mm}

\noindent \textit{\textbf{Markov Logic Network as an interface layer.}}
Markov logic is a language that combines first-order logic and Markov
networks. A knowledge base (KB) in Markov logic is a set of first-order formulas with weights. Given
a set of constants representing objects in the domain of interest, it defines a probability distribution
over possible worlds, each world being an assignment of truth values to all possible ground atoms. The
distribution is in the form of a log-linear model: a normalized exponentiated weighted combination
of features of the world. Each feature is a grounding of a formula in the KB, with the corresponding
weight. More details can be found in~\cite{mln}.

We argue that Markov logic network (MLN) can naturally serve as an interface layer of
testing-based bug localization. Here are the major reasons:

\begin{itemize}

\item Testing-based software bug localization is essentially a probabilistic treatment of program
entities (e.g., predicates, statements, methods) that model how a program entity is evaluated in
multiple evaluations during a set passing/failing executions. On top of the probability treatment
of program entities, a well-designed ranking algorithm that ranks program entities according to how
abnormally they are in the observed executions. The more abnormal the evaluations, the more likely
it is relevant to the bug. Thus, a desirable interface layer must permit users to easily
specify  relations between program entities and observed test executions. On the other hand, each
program entity is unlikely to be isolated from one other; a bug is often triggered as state transitions from
one program entity to another before the bug becomes apparent. Therefore, an interface layer must also permit
users to specify relations between different program entities.


\item From a dynamic viewpoint, a software system keeps evolving as new features are added, and existing
bugs are fixed. When a new bug occurs, it is likely that a similar bug has already been detected and
confirmed in the past. Learning from bugs with similar symptoms, a testing-based bug localization
can leverage past solutions to the current problem improve its effectiveness. Thus, when designing
new techniques, an interface layer should also permit programmers to utilize prior
knowledge to aid bug localization.

\item In MLN, a knowledge base is a set of first-order formulas with weights. Formulas are soft constraints: a world that violates a formula is less
probable than one that satisfies it, other things being equal, but not impossible.
Markov logic allows an existing first-order KB to be transformed
into a probabilistic model simply by assigning weights to the formulas, manually or by learning
them from data. On the statistical side, it allows very complex models to be represented very compactly,
and facilitates the incorporation of rich domain knowledge, reducing reliance on purely empirical learning.
This permits users to easily and naturally specify relations between program entities and test
observations.

Additionally, in MLN, the formulas and weights of the
supporting knowledge bases can be adjusted based on data from the new task. New knowledge
is added by noting and correcting the failures of the induced and refined KBs, and the process repeats.
This permits users to leverage and customize prior knowledge for more effective bug localization techniques.

Furthermore, MLN is supported by a full range of learning
and inference algorithms, in each case combining logical and statistical elements. Because of its
generality, it provides a natural framework for integrating the logical and statistical approaches in
each field. This makes MLN independent of any specific learning/inference algorithms. Users can
pick the most suitable ones for the current task.

All above good characteristics of MLN make it suitable as an interface layer for testing-base bug
localization.


\end{itemize}

